﻿#include<iostream>
#include<vector>
#include<queue>

struct TreeNode {
	int val;
	TreeNode* leftNode;
	TreeNode* rightNode;

	TreeNode(int _val) :val(_val), leftNode(nullptr), rightNode(nullptr) {

	}
};

//层序遍历
std::vector<int> levelOrder(TreeNode* root) {
	std::queue<TreeNode*> queue;
	//插入根节点
	queue.push(root);
	//新建动态数组
	std::vector<int> vec;
	while (!queue.empty()) {
		TreeNode* node = queue.front();
		//队首元素出队
		queue.pop();
		vec.push_back(node->val);

		if (node->leftNode != nullptr)
			queue.push(node->leftNode);
		if (node->rightNode != nullptr)
			queue.push(node->rightNode);
	}
	return vec;
}
//前序遍历 根 - 左 - 右
void preOrder(TreeNode* root) {	
	if (root == nullptr)
		return;
	std::vector<int> vec;
	vec.push_back(root->val);
	//左子节点
	preOrder(root->leftNode);
	//右子节点
	preOrder(root->rightNode);
}

//中序遍历 左 - 根 - 右
void inOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	std::vector<int> vec;
	inOrder(root->leftNode);
	vec.push_back(root->val);
	inOrder(root->rightNode);
}

//后序遍历 左 - 右 - 根
void postOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	std::vector<int> vec;
	postOrder(root->leftNode);
	postOrder(root->rightNode);
	vec.push_back(root->val);
}


int main() {

	TreeNode* n1 = new TreeNode(1);
	TreeNode* n2 = new TreeNode(2);
	TreeNode* n3 = new TreeNode(3);
	TreeNode* n4 = new TreeNode(4);
	TreeNode* n5 = new TreeNode(5);

	//根节点
	n1->leftNode = n2;
	n1->rightNode = n3;
	//左节点
	n2->leftNode = n4;
	n2->rightNode = n5;
	//插入
	TreeNode* node = new TreeNode(0);
	n1->leftNode = node;
	node->leftNode = n2;
	//删除
	n1->leftNode = n2;
	delete node;



	std::cout << "binary tree" << std::endl;
}